# -*- coding: utf-8 -*-

from math import *


#----------------------------------------------------------------------
# 求n的阶乘。
#
def factorial(n):
    if n <= 1:
        return n
    
    fac = n
    while n > 2:
        fac = fac * (n - 1)
        n = n - 1
        
    return fac

#----------------------------------------------------------------------
# 从m个元素中取出n个元素的组合的个数。
#
def combination(m, n):
    fac_m = factorial(m)
    fac_n = factorial(n)
    fac_m_sub_n = factorial(m - n)
    
    return  (fac_m / (fac_n * fac_m_sub_n))


#----------------------------------------------------------------------
# 将十进制数n转成二进制数。
#
def decimal_to_binary(n):
    pass

def d2b(n):
    decimal_to_binary(n)
    
#----------------------------------------------------------------------
# 将二进制数n转成十进制数。
#
def binary_to_decimal(n):
    pass
    
def b2d(n):
    binary_to_decimal(n)

#----------------------------------------------------------------------
# 求n的开根号。
#
def square(n):
    
    pass


#----------------------------------------------------------------------
# 判断正整数n是否是素数，即只能被其自身和1整除。
# 试除法：尝试从2到根号n的整数是否整除n。
#
def is_prime(n):
    if n == 1: return False
    elif n < 4: return True
    else:
        top = int(sqrt(n))
        for i in range(2, top + 1):
            pair = divmod(n, i)
            if pair[1] == 0:
                return False
        return True
"""
1 is not a prime.
All primes except 2 are odd.
All primes greater than 3 can be written in the form 6k+/-1.
Any number n can have only one primefactor greater than n .
The consequence for primality testing of a number n is: if we cannot find a number f less than
or equal n that divides n then n is prime: the only primefactor of n is n itself
"""
def is_prime_2(n):
    if n==1:
        return False
    elif n < 4: # 2, 3
        return True
    elif mod(n, 2) == 0:
        return False
    elif n < 9 :
        return True
    elif mod(n, 3) == 0:
        return False
    else:
        top = int(sqrt(n))
        f = 5
        while f <= top:
            if mod(n, f) == 0: return False
            if mod(n, f + 2) == 0: return False
            f = f + 6
        return True
    return False
    
#----------------------------------------------------------------------
# 整数分解(质因子分解)问题是指：给出一个正整数，将其写成几个素数的乘积。 
# Integer Factorization。
#
# 求n的质因子分解。
#
def int_fact(n):
    pass


#----------------------------------------------------------------------
# 最大公因子，指某几个整数共有因子中最大的一个。
# Greatest Common Divisor，简写为G.C.D.；
# 或Highest Common Factor，简写为H.C.F.）。
# 
# 求a和b的最大公因子。
#
# 短除法实现。
# 从1开始，逐个判断是否存在一个数可以整除a和b。
#
def gcd(a, b):
    array = []
    for i in range(1, min(a, b) + 1):
        pair1 = divmod(a, i)
        pair2 = divmod(b, i)
        if pair1[1] == 0 and pair2[1] == 0:
            array.append(i)
        array.sort()
    return array[len(array) - 1]

#
# 辗转相除法求最大公因子。
#
def gcd2(a, b):
    if a == b:
        return a
    elif a < b:
        t = b
        b = a
        a = t
        
    pair = divmod(a, b)
    if pair[1] == 0:
        return b
    
    return gcd2(b, pair[1])
    


#----------------------------------------------------------------------
# 最小公倍数，即两个整数共有倍数中最小的一个。
# Least Common Multiple 或者 Lowest Common Multiple，简写为L.C.M。
#
# 求a和b的最小公倍数。
#
def lcm(a, b):
    return (a * b) / gcd(a, b)






